As is well known, a solid state drive (SSD) is a data storage device that uses a NAND-based flash memory to store data. The NAND-based flash memory is a non-volatile memory. After data are written to the flash memory, if no power is supplied to the flash memory, the data are still retained in the flash memory.
FIG. 1 is a schematic functional block diagram illustrating a conventional solid state drive. As shown in FIG. 1, the solid state drive 10 comprises a controlling unit 101, a temporary storage unit 103, and a flash memory 105. The flash memory 105 is accessible by the controlling unit 101 through an internal bus 107. In addition, the controlling unit 101 is in communication with a host 12 through an external bus 20. Consequently, commands and data can be exchanged between the controlling unit 101 and the host 12. The temporary storage unit 103 is a random access memory for temporarily storing the read date, the write data or the temporary parameter which is required for the controlling unit 101. Moreover, the external bus 20 is a USB bus, an IEEE 1394 bus, an SATA bus, or the like.
Generally, the flash memory 105 comprises plural blocks. Each block comprises plural pages (or sectors), for example 64 pages. Each page is typically 4K bytes in size. Due to the inherent properties of the flash memory 105, at least one page is written at a time during the writing operation, but a block is erased during the erasing operation.
Due to the inherent properties of the flash memory 105, the data of each page fails to be arbitrarily refreshed. Consequently, after a refreshed data is received by the flash memory 105, the refreshed data is firstly stored in a new page (i.e. a blank page), and the original data in the old page is set as an invalid data. After the data of all pages of a whole block are invalid data, the block is erased as a free block.
However, after the flash memory 105 has been accessed for a long time, each block of the flash memory 105 may contain some valid data and some invalid data. The block containing the valid data fails to be erased.
Since the space of the flash memory 105 is occupied by the invalid data, the writable space of the flash memory is gradually reduced. For solving the above drawbacks, a garbage collection has been disclosed. Hereinafter, a garbage collection process will be illustrated with reference to FIGS. 2A˜2F. It is assumed that the flash memory 105 has eight blocks (Block_1˜Block_8) and each of the blocks has four pages (Page_1˜Page_4). It is noted that the number of blocks and the number of pages in each block are not restricted.
FIGS. 2A˜2F schematically illustrate a process of refreshing, moving and erasing data of a flash memory of a solid state drive. The architecture of the solid state drive is similar to that of the solid state drive of FIG. 1, and is not redundantly described herein.
As shown in FIG. 2A, all pages of the first block (Block_1) store the data Data1˜Data4, and all pages of the second block (Block_2) store the data Data5˜Data8.
In a case that the host 12 wants to refresh the data Data1 , Data2, Data4, Data6 and Data7 into the data Data1′, Data2′, Data4′, Data6′ and Data7′, respectively, the refreshed data will be stored in blank pages of the flash memory by the controlling unit 101 (see FIG. 2B). For example, the data Data1′ is written into the second page (page_2) of the fourth block (Block_4), the data Data2′ is written into the third page page_3 of the fifth block (Block_5), the data Data4′ is written into the second page (page_2) of the seventh block (Block_7), the data Data6′ is written into the second page (page_2) of the sixth block (Block_6), and the data Data7′ is written into the third page (page_3) of the sixth block (Block_6). From now on, the pages originally storing the data Data1, Data2, Data4, Data6 and Data7 are considered as invalid pages, which are indicated by oblique lines.
In case that the host 12 wants to refresh the data Data1′, Data2′, Data4′, Data6′ and Data7′ into the data Data1″, Data2″, Data4″, Data6″ and Data7″, respectively, the refreshed data will be stored in blank pages of the flash memory by the controlling unit 101 (see FIG. 2C). For example, the data Data1″ is written into the second page (page_2) of the fifth block (Block_5), the data Data2″ is written into the first page (page_1) of the fourth block (Block_4), the data Data4″ is written into the first page (page_1) of the sixth block (Block_6), the data Data6″ is written into the second page (page_2) of the third block (Block_3), and the data Data7″ is written into the fourth page (page_4) of the sixth block (Block_6). From now on, the data pages originally storing the data Data1′, Data2′, Data4′, Data6′ and Data7′ are considered as invalid pages, which are indicated by oblique lines.
In case that the host 12 wants to refresh the data Data7″ into the data Data7′″, the refreshed data will be stored in a blank page of the flash memory by the controlling unit 101 (see FIG. 2D). For example, the data Data7′″ is written into the fourth page (page_4) of the fourth block (Block_4). From now on, the data page originally storing the data Data7″ is considered as an invalid page, which is indicated by an oblique line.
From the above discussions, after many times of accessing operations by the host 12, the flash memory 105 may contain a great number of invalid data (see the oblique lines as shown in FIG. 2D). Moreover, the erasing operation of the flash memory 105 can be performed in a block-wise fashion. Although the flash memory as shown in FIG. 2D has many invalid data, some blocks still contain valid data. In other words, the block containing the valid data fails to be erased by the controlling unit 101. Since the space of the flash memory is occupied by the invalid data, the writable space of the flash memory is gradually reduced.
Consequently, for avoiding reduction of the writable space, the garbage collection should be performed by the controlling unit 101 of the solid state drive 10 at the appropriate time. The garbage collection is a process of collecting valid data of the old block and storing the valid data into another new block by the controlling unit 101. After the valid data are collected and re-stored, the data of all pages of the old block are changed into the invalid pages, so that the old block may be erased and reused as a free block. Under this circumstance, the writable space of the flash memory is enhanced. Moreover, after the garbage collection is done, the space of the new free block becomes the available space again.
For example, after the situation of FIG. 2D, the controlling unit 101 starts to perform the garbage collection. Consequently, the data Data3 in the third page (Page_3) of the first block (Block_1), the data Data5 in the first page (Page_1) of the second block (Block_2), the data Data8 in the fourth page (Page_4) of the second block (Block_2) and the data Data4″ in the first page (Page_1) of the sixth block (Block_6) will be collected and written into a blank eighth block (Block_8) by the controlling unit 101.
After the data Data3, Data5, Data8 and Data4″ are written into the eighth block (Block_8), all data in the first block (Block_1), the second (Block_2) and the sixth block (Block_6) of the flash memory 105 become invalid data (see FIG. 2E). Consequently, the controlling unit 101 may perform the block-erasing operation on the first block (Block_1), the second block (Block_2) and the sixth block (Block_6). Then, as shown in FIG. 2F, the first block (Block_1), the second block (Block_2) and the sixth block (Block_6) become free blocks. Under this circumstance, the flash memory 105 releases more writable space.
From the above discussions, the garbage collection may release more writable space of the flash memory 105. However, if the flash memory 105 is a larger-capacity memory, the flash memory 105 may have at least several thousands of blocks. Before the garbage collection is performed by the solid state drive 10, the controlling unit 101 should check the valid data of each block sequentially, and select the block with low valid data count to be subject to the garbage collection. In other words, the number of valid data to be moved should be as low as possible.
Since the information of the valid data of each block should be successively searched during each garbage collection, it is time-consuming for the controlling unit 101 to search the information. In other words, the conventional method of controlling the garbage collection is not efficient.